package Hot100.leetcode.editor.cn.code.前缀和;
//Java：除自身以外数组的乘积
public class ProductOfArrayExceptSelf{
    public static void main(String[] args) {
        Solution solution = new ProductOfArrayExceptSelf().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。
        // 换句话说，如果知道了 i 左边所有数的乘积，以及 i 右边所有数的乘积，就可以算出 answer[i]。
        //于是：
        //定义 pre[i] 表示从 nums[0] 到 nums[i−1] 的乘积。
        //定义 suf[i] 表示从 nums[i+1] 到 nums[n−1] 的乘积。
        //我们可以先计算出从 nums[0] 到 nums[i−2] 的乘积 pre[i−1]，再乘上 nums[i−1]，就得到了 pre[i]，即
        //
        //pre[i]=pre[i−1]⋅nums[i−1]
        //同理有
        //suf[i]=suf[i+1]⋅nums[i+1]

    //pre[0]=suf[n−1]=1。按照上文的定义，pre[0] 和 suf[n−1] 都是空子数组的元素乘积 因为我们这里是乘机，乘机是不变的没事
        //这样可以方便递推计算 pre[1]，suf[n−2] 等
    public int[] productExceptSelf(int[] nums) {
        //不优化版分开算好 pre[] 和 suf[] 然后遍历相乘
        //优化版在计算suf以后都要最后遍历乘顺便把pre乘进来省略了一次遍历
        int n = nums.length;
        //元素的下标对应前后缀合数组的取值
        int[] suf = new int[n];
        suf[n-1] = 1;
        for (int i = n -2 ; i >= 0; i--) {
            suf[i] = suf[i+1] * nums[i+1];
        }

        int pre = 1;
        for (int i = 0; i < n; i++) {
            //我们直接对suf数组进行覆盖返回值
            suf[i] *= pre;
            //因为刚好遍历前缀和本身也就是顺序一个个相乘
            pre *= nums[i];
        }

        return suf;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}